home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Applications / Newswatcher 2.0b22 / NW Source / Source / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-18  |  5.6 KB  |  215 lines  |  [TEXT/MMCC]
  1. /*----------------------------------------------------------------------------
  2.  
  3.     qsort.c
  4.  
  5.     This reusable module implements a fast quicksort algorithm.
  6.  
  7.     fastQSort() is a replacement for qsort().  Compared with the Think C library
  8.     version of qsort, fastQSort is about 3 times faster (it takes 1/3 the time), 
  9.     and its speed isn't dependent on the data being sorted.
  10.     
  11.     One problem with qsort is that when the data is not in random order -- for
  12.     example when it's already ordered, in reverse order, or almost sorted -- then 
  13.     qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can 
  14.     take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort 
  15.     algorithm doesn't have this problem, because it randomly selects the pivot
  16.     element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.
  17.     
  18.     Also, because fastQSort doesn't exhibit worst case behavior, it doesn't 
  19.     require as much stack space, even though it has 12 bytes more of local
  20.     variables.
  21.     
  22.     The things that make fastQSort so much faster than qsort are:
  23.     
  24.     1)    fastQSort picks the pivot element randomly, so it doesn't display worst
  25.         case behavior.
  26.         
  27.     2)    fastQSort uses pointers and pointer arithmetic, avoiding multiplication
  28.         whenever possible.
  29.     
  30.     3)    qsort uses std_swap() to swap the data between two locations, and 
  31.         std_swap loops through the data 3 times to perform the exchange!  In
  32.         comparison, swapMem() loops through the data just once.
  33.         
  34.     4)    fastQSort uses register variables whenever it makes good sense to do so.
  35.     
  36.     
  37.     Researched and written by:
  38.     
  39.         Haydn Huntley
  40.         Haydn's Consulting
  41.         203 West Stone
  42.         Fairfield, Iowa  52556
  43.         (515) 472-7025
  44.         
  45.     During the school year, I may be reached at the following address:
  46.     
  47.         Haydn Huntley
  48.         Eigenmann Hall #289
  49.         Indiana University
  50.         Bloomington, IN  47406
  51.         (812) 857-8620
  52.         
  53.     E-mail:  huntley@copper.ucs.indiana.edu
  54. ----------------------------------------------------------------------------*/
  55.  
  56. #include <stdlib.h>
  57.  
  58. #include "def.h"
  59. #include "qsort.h"
  60.  
  61.  
  62.  
  63. static size_t gSize;
  64. static short (*gCmpFn)(void *, void *);
  65. static Boolean gCancel;
  66.  
  67.  
  68.  
  69. /*----------------------------------------------------------------------------
  70.     MemSwap 
  71.     
  72.     Exchange two array elements.
  73.             
  74.     Entry:    p = pointer to first element.
  75.             q = pointer to second element.
  76.             size = size of elements.
  77. ----------------------------------------------------------------------------*/
  78.  
  79. static void MemSwap (register char *p, register char *q, 
  80.     register size_t size)
  81. {
  82.     register char tmp;
  83.     
  84.     while (size--) {
  85.         tmp = *p;
  86.         *p++ = *q;
  87.         *q++ = tmp;
  88.     }
  89. }
  90.  
  91.  
  92.  
  93. /*----------------------------------------------------------------------------
  94.     ChooseMedian
  95.     
  96.     Select the median of three array elements and swap it with a destination
  97.     element.
  98.     
  99.     Entry:    pDest = pointer to destination element.
  100.             pA, pB, pC = pointer to three elements.
  101. ----------------------------------------------------------------------------*/
  102.  
  103. static void ChooseMedian (void *pDest, void *pA, void *pB, void *pC)
  104. {
  105.     void *pMedian;
  106.     
  107.     if (gCmpFn(pA, pB) > 0)                    /* pA > pB, what is pC?            */
  108.         if (gCmpFn(pA, pC) > 0)                /* pA > pB, pA > pC                */
  109.             if (gCmpFn(pB, pC) > 0)
  110.                 pMedian = pB;                /* pA > pB > pC                    */
  111.             else
  112.                 pMedian = pC;                /* pA > pC > pB                    */
  113.         else
  114.             pMedian = pA;                    /* pC > pA > pB                    */
  115.     else                                    /* pB > pA, what is pC?            */
  116.         if (gCmpFn(pA, pC) > 0)
  117.             pMedian = pA;                    /* pB > pA > pC                    */
  118.         else                                /* pB > pA, pC > pA                */
  119.             if (gCmpFn(pB, pC) > 0)
  120.                 pMedian = pC;                /* pB > pC > pA                    */
  121.             else
  122.                 pMedian = pB;                /* pC > pB > pA                    */
  123.  
  124.     if (pDest != pMedian) MemSwap(pDest, pMedian, gSize);
  125. }
  126.  
  127.  
  128.  
  129. /*----------------------------------------------------------------------------
  130.     DoFastQSort
  131.     
  132.     Entry:    first = pointer to first element 
  133.                 of array in range to be sorted.
  134.             last = pointer to element following last element
  135.                 of array in range to be sorted. 
  136. ----------------------------------------------------------------------------*/
  137.  
  138. static void DoFastQSort (register char *first, char *last)
  139. {
  140.     register char *i, *j;
  141.     register size_t    n, qSize = gSize;
  142.          
  143.     while (!gCancel && (n = (last - first) / qSize) > 1) {
  144.         if (n < 25) {
  145.             MemSwap(first + (rand() % n) * qSize, first, qSize);
  146.         } else {
  147.             ChooseMedian(first, first, first + (n / 2) * qSize, 
  148.                 first + (rand() % n) * qSize);
  149.         }
  150.         i = first;
  151.         j = last;
  152.         while (true) {
  153.             i += qSize;
  154.             while (i < last && gCmpFn(i, first) < 0) i += qSize;
  155.             j -= qSize;
  156.             while (j > first && gCmpFn(j, first) > 0) j -= qSize;
  157.             if (i >= j) break;
  158.             MemSwap(i, j, qSize);
  159.         }
  160.         if (j == first) {
  161.             first += qSize;
  162.             continue;
  163.         }
  164.         MemSwap(first, j, qSize);
  165.         if (j - first < last - (j + qSize)) {
  166.             DoFastQSort(first, j);
  167.             first = j + qSize;
  168.         } else {
  169.             DoFastQSort(j + qSize, last);
  170.             last = j;
  171.         }
  172.     }
  173. }
  174.  
  175.  
  176.  
  177. /*----------------------------------------------------------------------------
  178.     FastQSort
  179.     
  180.     Sort an array.
  181.     
  182.     Entry:    base = pointer to first array element.
  183.             n = number of array elements.
  184.             size = size of array elements.
  185.             cmpFn = pointer to array element comparison function.
  186.             
  187.     Exit:    function result = error code (noErr if sorted, userCanceledErr
  188.                 if canceled by user). 
  189. ----------------------------------------------------------------------------*/
  190.  
  191. OSErr FastQSort (void *base, size_t n, size_t size, 
  192.     short (*cmpFn)(void *, void *))
  193. {
  194.     gSize = size;
  195.     gCmpFn = cmpFn;
  196.     gCancel = false;
  197.     srand(TickCount());
  198.     
  199.     DoFastQSort (base, (char*)base + n * gSize);
  200.     
  201.     return gCancel ? userCanceledErr : noErr;
  202. }
  203.  
  204.  
  205.  
  206. /*----------------------------------------------------------------------------
  207.     CancelFastQSort
  208.     
  209.     Cancel a sort. 
  210. ----------------------------------------------------------------------------*/
  211.  
  212. void CancelFastQSort (void)
  213. {
  214.     gCancel = true;
  215. }